5327. Скобочные последовательности

 

Скобочная последовательность – это правильное арифметическое выражение, из которого удалены все числа и знаки операций. Например,

1 + ( ( ( 2 + 3 ) + 5 ) + ( 3 + 4 ) ) → ( ( ( ) ) ( ) )

 

Вход. Задана последовательность из открывающихся и закрывающихся скобок длиной не более 4 * 106.

 

Выход. Выведите “YES”, если скобочная последовательность правильная, и “NO” иначе.

 

Пример входа 1

Пример выхода 1

((())())

YES

 

 

Пример входа 2

Пример выхода 2

(()

NO

 

 

РЕШЕНИЕ

стек

 

Анализ алгоритма

Объявим стек, в который будем помещать только открывающиеся скобки. При поступлении очередного символа выполняем следующую операцию со стеком:

·        если встречается символ ‘(‘, то заносим его в стек;

·        если встречается символ ‘)‘, то извлекаем элемент из стека. Если при этом стек оказывается пустым, то последовательность не является скобочной (на некотором этапе количество закрывающихся скобок превышает количество открывающихся);

По окончании обработки строки стек должен оставаться пустым.

 

Моделирование стека можно осуществить с использованием единственной переменной. Пусть переменная cnt хранит количество открытых скобок в стеке. Тогда при помещении символа ‘(‘ в стек увеличим cnt на 1, а при извлечении элемента из стека – уменьшаем cnt на 1.

 

Пример

Промоделируем работу стека для строки “((())())” из первого примера.

 

Реализация алгоритма

Читаем входную строку.

 

cin >> s;

 

Переменная cnt хранит количество текущих незакрытых скобок (то есть количество открывающихся скобок, для которых еще не встретились соответствующие закрывающиеся скобки).

Переменная flag устанавливается в 1, если на какой-то итерации количество закрывающихся скобок становится больше числа открывающихся. Изначально установим flag = 0.

 

cnt = flag = 0;

 

Обрабатываем входную строку посимвольно, моделируя работу со стеком.

 

for (i = 0; i < s.size(); i++)

{

 

Обрабатываем текущий символ s[i].

 

   if (s[i] == '(') cnt++; else cnt--;

 

Если количество закрывающихся скобок в некоторый момент времени становится больше числа открывающихся, то входная последовательность не является скобочной.

 

   if (cnt < 0) flag = 1;

}

 

В зависимости от значений переменных flag и cnt выводим ответ. Стек будет пустым в конце обработки строки, если cnt = 0.

 

if (flag == 0 && cnt == 0)

  cout << "YES\n"; else cout << "NO\n";

 

Java реализация через строку

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    String s = con.nextLine();

 

    boolean flag = false;

    int open  = 0;

    for(int i = 0; i < s.length(); i++)

    {

      if (s.charAt(i) == '(')

        open++;

      else

        open--;

      if (open < 0)

        flag = true;

    }

 

    if (flag || (open > 0))

      System.out.println("NO");

    else

      System.out.println("YES");

    con.close(); 

  }

}   

 

Java реализация через массив символов

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    char s[] = con.nextLine().toCharArray();

 

    boolean flag = false;

    int open  = 0;

    for(int i = 0; i < s.length; i++)

    {

      if (s[i] == '(')

        open++;

      else

        open--;

      if (open < 0)

        flag = true;

    }

 

    if (flag || (open > 0))

      System.out.println("NO");

    else

      System.out.println("YES");

    con.close(); 

  }

}   

 

Python реализация

Читаем входную строку.

 

s = input()

 

Переменная cnt хранит количество текущих незакрытых скобок (то есть количество открывающихся скобок, для которых еще не встретились соответствующие закрывающиеся скобки).

Переменная flag устанавливается в 1, если на какой-то итерации количество закрывающихся скобок становится больше числа открывающихся. Изначально установим flag = 0.

 

cnt = flag = 0

 

Обрабатываем входную строку посимвольно, моделируя работу со стеком.

 

for ch in s:

 

Обрабатываем текущий символ s[i].

 

  if ch == '(': cnt += 1

  else: cnt -= 1

 

Если количество закрывающихся скобок в некоторый момент времени становится больше числа открывающихся, то входная последовательность не является скобочной.

 

  if cnt < 0: flag = 1

 

В зависимости от значений переменных flag и cnt выводим ответ. Стек будет пустым в конце обработки строки, если cnt = 0.

 

if flag == 0 and cnt == 0:

  print("YES")

else:

  print("NO")